package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold'>大小为 K 且平均值大于等于阈值的子数组数目(Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold)</a>
 * <p>给你一个整数数组 arr 和两个整数 k 和 threshold 。</p>
 * <p>请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
 *      输出：3
 *      解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
 *
 *  示例 2：
 *      输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
 *      输出：6
 *      解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= arr.length <= 10^5</li>
 *     <li>1 <= arr[i] <= 10^4</li>
 *     <li>1 <= k <= arr.length</li>
 *     <li>0 <= threshold <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/30 10:54
 */
public class LC1343NumberOfSubarraysOfSizeKAverageGelThreshold_M {
    static class Solution {
        public int numOfSubarrays(int[] arr, int k, int threshold) {
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += arr[i];
            }
            int target = k * threshold;
            int res = sum >= target ? 1 : 0;
            for (int i = k; i < arr.length; i++) {
                sum += arr[i] - arr[i - k];
                if (sum >= target) {
                    ++res;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numOfSubarrays(new int[]{2, 2, 2, 2, 5, 5, 5, 8}, 3, 4));
        System.out.println(solution.numOfSubarrays(new int[]{11, 13, 17, 23, 29, 31, 7, 5, 2, 3}, 3, 5));
    }
}
